import com.sun.istack.internal.localization.NullLocalizable;

public class M如何展开链接列表 {

    private class Node {
        int data;
        Node right, down;

        Node(int data) {
            this.data = data;
            this.right = null;
            this.down = null;
        }
    }

    private Node head;

    //用来合并两个有序的链表
    private Node merge(Node a, Node b) {

        //如果有其中一个链表为空，直接返回另外一个链表
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }

        Node result;
        if (a.data < b.data) {
            result = a;
            result.down = merge(a.down, b);
        } else {
            result = b;
            result.down = merge(a, b.down);
        }
        return result;
    }

    //把链表扁平化处理
    public Node flattern(Node root) {
        if (root == null || root.right == null) {
            return root;
        }
        //递归处理root.right链表
        root.right = flattern(root.right);
        //把root节点对应的链表与右边的链表合并
        root = merge(root, root.right);
        return root;
    }

    private Node insert(Node head_ref, int data) {
        Node new_node = new Node(data);
        new_node.down = head_ref;
        head_ref = new_node;
        return head_ref;
    }

    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.down;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        M如何展开链接列表 l = new M如何展开链接列表();
        l.head = l.insert(l.head, 31);
        l.head = l.insert(l.head, 8);
        l.head = l.insert(l.head, 6);
        l.head = l.insert(l.head, 3);

        l.head.right = l.insert(l.head.right, 21);
        l.head.right = l.insert(l.head.right, 11);

        l.head.right.right = l.insert(l.head.right.right, 50);
        l.head.right.right = l.insert(l.head.right.right, 22);
        l.head.right.right = l.insert(l.head.right.right, 15);

        l.head.right.right.right = l.insert(l.head.right.right.right, 55);
        l.head.right.right.right = l.insert(l.head.right.right.right, 40);
        l.head.right.right.right = l.insert(l.head.right.right.right, 39);
        l.head.right.right.right = l.insert(l.head.right.right.right, 30);
        //扁平化链表
        l.head = l.flattern(l.head);
        l.printList();

    }
}
